#define _CRT_SECURE_NO_WARNINGS 1

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* partition(struct ListNode* head, int x) {
    if (head == NULL || head->next == NULL)
        return head;
    struct  ListNode* ptail = head, * p_big = NULL, * p_small = NULL, * big_head = NULL;
    while (ptail)
    {
        if (ptail->val >= x)
        {
            if (p_big == NULL)
            {
                p_big = ptail;
                big_head = ptail;
            }
            else
            {
                p_big->next = ptail;
                p_big = p_big->next;
            }
        }
        else
        {
            if (p_small == NULL)
            {
                p_small = ptail;
                head = ptail;
            }
            else
            {
                p_small->next = ptail;
                p_small = p_small->next;
            }
        }
        ptail = ptail->next;
    }
    if (p_big != NULL)
        p_big->next = NULL;
    if (p_small != NULL)
        p_small->next = big_head;
    return head;
}